package com.zlk.algorithm.huawei.leetcode.binaryTree;

import com.zlk.algorithm.util.TreeNode;

import java.util.HashMap;

/**
 * @program: algorithm
 * @ClassName Coode_31pathSum
 * @description:路径总和 III  todo
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，
 * 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，
 * 但是路径方向必须是向下的（只能从父节点到子节点）。
 * @author: slfang
 * @create: 2025-01-09 16:43
 * @Version 1.0
 **/
public class Code31_pathSum {

//    public int pathSum(TreeNode root, int targetSum) {
//        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
//        prefix.put(0L, 1);
//        return dfs(root, prefix, 0, targetSum);
//    }
//
//    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
//        if (root == null) {
//            return 0;
//        }
//
//        int ret = 0;
//        curr += root.val;
//
//        ret = prefix.getOrDefault(curr - targetSum, 0);
//        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
//        ret += dfs(root.left, prefix, curr, targetSum);
//        ret += dfs(root.right, prefix, curr, targetSum);
//        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
//
//        return ret;
//    }


    int count=0;
    TreeNode head;
    public int pathSum(TreeNode root, int targetSum) {
        //构建前准树
        HashMap<TreeNode,Integer> sumMap = new HashMap<>();
        head = root;
        int pre = 0;
        setPreTree(root,pre,sumMap);
        getCount(root,targetSum);
        return -1;

    }

    private void getCount(TreeNode root,int targetSum) {
        if(root==null){
            return ;
        }
        if(root.val==targetSum){
            count++;
        }

        getCount(root.left,targetSum);
        getCount(root.right,targetSum);
    }

    private void setPreTree(TreeNode root, int pre, HashMap<TreeNode, Integer> sumMap) {
        if(root!=null){
            return ;
        }
        root.val +=pre;
        pre = root.val;
        sumMap.put(root,pre);
        setPreTree(root.left,pre, sumMap);
        setPreTree(root.right,pre, sumMap);
    }
}


